/*
	计算花费的代价推导:
	e= Σ(dep(k[i]+1)*p[i]) + Σ(dep(d[i]+1)*q[i])   式子1
	  i(1->n)               i(0->n)
	因为 
	  	Σp[i]+Σq[i] = 1                            式子2  
	所以
	e= 1+  Σ(dep(k[i])*p[i]) + Σ(dep(d[i])*q[i])   式子3
	      i(1->n)             i(0->n)


	e[i][j]:表示为包含关键字k(i),k(i+1),,,k(j)的最优二叉树所花费的代价
			对于给定的k(1),,,k(n),则问题的解为e[1][n]
	当j=i-1时,子树只包含伪关键字d(i-1)
	当j>-i 时,需要从k(i),,,k(j)中选择一个结点做根结点,记做k(r)
	         然后继续构造一颗以包含k(i),,,k(r-1)的最优二叉左子树
	         再构造一颗以包含k(r+1),,,k(j)的最优二叉右子树

	对于上述 式子2 
	k(i)到k(j)的关键字的概率和公式构造为
		w[i][j] = Σp[]  +   Σq[]
				 (i->j)   (i-1 ->j) 

	因此问题解转为 式子3 :
	e[i,j] = w[i][j]+  Σ(dep(k[i])*p[i]) + Σ(dep(d[i])*q[i])
		   = p(r) + (e[i][r-1] + w[i][r-1]) + (e[r+1][j] + w[r+1][j])
	w[i][j] = w[i][r-1] + p[r] + w[r+1][j]
	即
	e[i][j] = e[i][r-1] + e[r+1][j] + w[i][j]

	因为r是假定选取的,要找出最小值的解为
	当j=i-1, e[i][j] = q[i-1]
	当j>=i , e[i][j] = min{e[i][r-1] + e[r+1][j] + w[i][j]}
*/

int optimal_BST(double *p, double *q, int n, double **w, double **e, int **s)
{
	for(int i = 1; i <= n+1; i++)
	{/*
		第一维下标上界为n+1而不是n，
		原因:
		1.对于只包含伪关键字d(n)的子树，我们需要计算并保存e[n+1,n]。
		2.第二维下标下界为0，是因为对于只包含伪关键字d0的子树，
		我们需要计算并保存e[1,0]
	*/
		w[i][i-1] = q[i-1];
		e[i][i-1] = q[i-1];
	}

	for(int r = 0; r < n; r++)//问题规模
	{
		for(int i = 1; i <= n-r; i++)
		{
			int j = i+r;
			e[i][j] = e[i][];
			w[i][j] = w
		}
	}
}